The Itoh–Tsujii inversion algorithm is used to invert elements in a
finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
. It was introduced in 1988, first over GF(2
''m'') using the
normal basis In mathematics, specifically the algebraic theory of fields, a normal basis is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any ...
representation of elements, however, the algorithm is generic and can be used for other bases, such as the
polynomial basis
In mathematics the monomial basis of a polynomial ring is its basis (as a vector space or free module over the field or ring of coefficients) that consists of all monomials. The monomials form a basis because every polynomial may be uniquely wr ...
. It can also be used in any finite field GF(''p''
''m'').
The algorithm is as follows:
: Input: ''A'' ∈ GF(''p''
''m'')
: Output: ''A''
−1
:# ''r'' ← (''p''
''m'' − 1)/(''p'' − 1)
:# compute ''A''
''r'' − 1 in GF(''p''
''m'')
:# compute ''A''
''r'' = ''A''
''r'' − 1 · ''A''
:# compute (''A''
''r'')
−1 in GF(''p'')
:# compute ''A''
−1 = (''A''
''r'')
−1 · ''A''
''r'' −1
:# return ''A''
−1
This algorithm is fast because steps 3 and 5 both involve operations in the subfield GF(''p''). Similarly, if a small value of ''p'' is used, a lookup table can be used for inversion in step 4. The majority of time spent in this algorithm is in step 2, the first exponentiation. This is one reason why this algorithm is well suited for the normal basis, since squaring and exponentiation are relatively easy in that basis.
See also
*
Finite field arithmetic In mathematics, finite field arithmetic is arithmetic in a finite field (a field containing a finite number of elements) contrary to arithmetic in a field with an infinite number of elements, like the field of rational numbers.
There are infin ...
References
* T. Itoh and S. Tsujii. A Fast Algorithm for Computing Multiplicative Inverses in GF(2
''m'') Using Normal Bases. ''Information and Computation'', 78:171–177, 1988.
{{DEFAULTSORT:Itoh-Tsujii inversion algorithm
Finite fields
Computational number theory